2023-04-14-wqs二分

我们有时候需要解决在一定限制下的最优化问题，通常它们可以写成如下形式：在的情况下使最小化（最大化）。

但是很多时候这样的问题难以直接解决，而相应的没有限制的问题通常会更容易解决（即求的最小值）。

所以如果能从无限制问题中的结果得到有限制问题的结果，我们就能更容易地解决原问题。

对于问题：使最小化，其中

考虑无限制问题：使最小化，其中。

若有满足的解，那也是原问题的一个解。

该定理可以用反证法简单地证明。

由上述定理可以看到，如果关于有单调性，就可以通过二分和解决（比简单）来找到答案

如果问题关于不同的限制具有凸性（a.k.a. ）那么关于就有单调性

一般来说，凸性可以通过暴力算法打印数据找规律~~猜蒙凑~~得出